#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10, M = 2 * N;
int dis[N], h[N], e[M], ne[M], idx;
int f[N][21];
int n, m;
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa)
{
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j != fa) {
			dis[j] = dis[u] + 1;
			f[j][0] = u;
			dfs(j, u);
		}
	}
}

int lca(int a, int b)
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < 20; j++) {
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	if (dis[a] < dis[b])swap(a, b);
	int d = dis[a] - dis[b];
	for (int i = 0; d; i++) {
		if (d & 1)a = f[a][i];
		d /= 2;
	}
	if (a == b)return a;
	for (int i = 19; i >= 0; i--) {
		if (f[a][i] != f[b][i]) {
			a = f[a][i];
			b = f[b][i];
		}
	}
	return f[a][0];
}
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		memset(h, -1, sizeof(h));
		memset(dis, 0, sizeof(dis));
		memset(e, 0, sizeof(e));
		memset(ne, 0, sizeof(ne));
		memset(f, 0, sizeof(f));
		idx = 0;
		for (int i = 1; i <= n; i++) {
			int a, b;
			cin >> a >> b;
			if (a != -1)add(i, a), add(a, i);
			if (b != -1)add(i, b), add(b, i);
		}
		dis[1] = 0;
		dfs(1, 0);
		//for (int i = 1; i <= n; i++)cout << "dis[i]=="<<dis[i]<<endl;
		while (m--) {
			int a, b;
			cin >> a >> b;
			int ans = lca(a, b);
			//cout<<"ans=="<<ans<<endl;
			cout << dis[a] + dis[b] - 2 * dis[ans] << endl;
		}
	}
	return 0;
}